package _0502_IPO;

import java.util.*;

/**
 * Date: 2021/9/8 9:34
 * Content:
 * 执行用时：85 ms, 在所有 Java 提交中击败了44.57%的用户
 * 内存消耗：57.4 MB, 在所有 Java 提交中击败了47.29%的用户
 */
public class Solution {

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        List<int[]> q = new ArrayList<>();
        int n = profits.length;
        for (int i = 0; i < n; i++) q.add(new int[]{capital[i], profits[i]});
        q.sort((a, b) -> a[0] - b[0]);

        Queue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        int i = 0;  // 记录可选的资本
        while (k-- != 0) {
            while (i < n && q.get(i)[0] <= w) heap.add(q.get(i++)[1]);
            if (heap.isEmpty()) break;
            int t = heap.remove();
            w += t;
        }
        return w;
    }
}
